1. Field of the Invention
The present invention pertains to the fields of computer systems, personal conferencing, and image processing. More particularly, this invention relates to the compression of image data for transfer between two agents.
2. Background
Computer technology is continuously advancing, providing newer computer systems with continuously improved performance. This improved performance is evidenced in a wide variety of characteristics. For example, the processing speeds of computer systems are increasing, the storage capabilities are increasing, and the visual display capabilities are increasing. One result of this improved performance is an increased use of computer systems by individuals in a wide variety of business, academic and personal applications.
One problem experienced in the advancement of computer technology is that the various characteristics which define a system's performance do not always advance at the same rate. For example, storage capabilities are not always being improved at the same rate as processing speed. Thus, although a computer system may utilize a high-performance processor, the storage device of the system (such as a hard disk) may be neither fast enough nor large enough to fully support the processor.
In addition, the increase in use of computer systems by individuals has found new and expanded areas of usage. One such area is that of personal conferencing, which is becoming increasingly demanded by computer users. Personal conferencing generally refers to two or more individual computer systems in communication with each other via a communication device. Such a communication device may be, for example, a telephone line or a local area network (LAN).
Although personal conferencing capabilities are increasingly demanded by computer users, the performance of communication devices do not always allow computer users to take full advantage of their computer systems. For example, the communication device(s) used to connect two computer systems may not be able to transfer data between the systems at the rate each system is able to transmit or receive and process data. Thus, two high-performance computer systems communicating with each other may not be able to operate at their optimal level; rather, they are required to accept the limitations found in the communication device(s) coupling them.
For example, increased processing speeds have supported an increase in visual display capabilities, as evidenced by an increase in both screen and color resolutions. Screen resolution refers to the number of pixels in a visual display. Each pixel is an individual screen location which can be illuminated or otherwise activated on the visual display, and can be represented by a unique (x,y) coordinate. Modern display capabilities include screen resolutions such as 640.times.480, 800.times.600, and 1024.times.768. Color resolution refers to the color depth of each pixel on the display; that is, the number of different colors each pixel can display. Modem computer systems can provide color resolutions in the order of millions of colors.
This increase in display capabilities, however, is accompanied by an increase in memory space required to store an image being displayed, or to be displayed, on the visual display. That is, a color must be stored for each pixel on the screen. For example, a display with 800.times.600 resolution contains 480,000 pixels, each of which can have any one of the available colors. If the display has a color resolution of 256 colors (which can be represented using 8 bits), then the storage size of an entire-screen image is approximately 500k bytes, which is the amount of memory necessary to store the image. Thus, it will be apparent that as the color resolution increases, the storage area required for an image increases dramatically.
The increase in required storage area generates two significant problems. First, the storage device (such as a disk or tape drive) must be large enough to store a sufficient number of images. The actual number of images is dependent on the users of the system. Second, the communication devices coupling multiple computer systems are relatively slow, compared to the processing capabilities of the computer systems. Thus, the time required to transfer such a large image between computer systems can be very long.
One technique used to solve both of these problems is that of data compression. Utilizing data compression techniques, the storage size of the image is reduced while maintaining the same resolution. Thus, the image utilizes a smaller amount of space in the storage device, and can be transferred via a communication device more quickly.
Two types of compression techniques are commonly used to compress images: lossless compression and lossy compression. In lossless compression, the storage size of the image is reduced without losing any data. That is, the image can be compressed, stored or transferred, then decompressed, and the decompressed image will be identical to the original image. In lossy compression, however, the size of the image is reduced and a small amount of data loss occurs. Thus, an image which is compressed, stored or transferred, and then decompressed will be slightly different from the original image. Although lossy compression causes some data loss, ideally that data loss is not evident to the user.
Both lossless and lossy compression processes typically work best in situations where the other works poorly. That is, when lossless compression works well, lossy compression generally works poorly, and vice versa. Lossless compression typically works well in situations where the data being compressed has significant entropy. Entropy refers to repetitions within the data. For example, an image comprising a total of 50 characters, each of which is different, would have low entropy, whereas an image comprising 10 occurrences each of five different characters would have higher entropy.
Lossy compression, however, typically works well in situations where the data being compressed has low entropy. In situations of low entropy, little of the data being compressed is repeated. An example of a low entropy image is a continuous-tone image with a color resolution of 16 million colors. Typically, in a continuous-tone image very few, if any, pixels have the same color. However, even though two adjacent pixels may have slightly different colors, the difference in color may not be noticeable to the human eye. Thus, in a wide variety of circumstances, the assumption is made that two pixels with slightly different colors can be treated as having the same color. Lossy compression takes advantage of this assumption and alters the colors of some of the pixels. Thus, some data loss occurs during compression, however ideally this data loss is not observable by the system user.
These compression techniques can be utilized both to transfer image data between two computer systems and to store image data in a storage device, thereby reducing transfer time and reducing storage requirements, respectively.
One technique for selecting between these image compression techniques is to always use one or the other. For example, if the system typically transfers images with high entropy, then the system uses lossless compression for all images. Alteratively, if the system typically transfers continuous-tone images, then the system uses lossy compression for all images. However, such a technique does not work well in systems which transfer both types of images because the system is tuned to optimize a particular type of image and provides poor performance for other types of images.
Generally, only one of these two compression techniques (lossless or lossy) works well on a particular image or portion of data. Thus, it would be beneficial to provide a system which optimally chooses between these techniques for each image being transferred or stored.
Another technique for selecting between these image compression techniques is to allow the system user to choose between them. That is, if the system user desires to use data compression, he or she is given a choice between the two compression techniques and must choose which one is used. This technique has several disadvantages. First, the system user may not understand which technique works best in which situations, and thus may not be qualified to make the choice. Second, the image may be such that, even if the user is qualified to choose, it may not be readily apparent which choice is correct. Third, the user is inconvenienced by having to make the choice. This inconvenience is especially true in situations where the user is transferring a large number of images, and is required to make a choice for each of the images being transferred. Fourth, the speed of the system is decreased due to the requisite decision time of the user. One goal of compression is to increase the speed of data transfers; thus, the time required by the user to select a compression technique hinders attaining this goal.
Another technique for selecting an image compression process is an adaptive technique which partitions an image into multiple smaller sections. A first section is compressed using one particular compression algorithm, and if the algorithm worked well, then that same compression algorithm is used for the next section. If the compression algorithm did not work well, then another algorithm is chosen to compress the next section. The first section is not recompressed using a different algorithm. This process proceeds for each section in the image, with the compression algorithm for one section being dependent on the success of the compression of the previous section. This adaptive technique may also be applied to a series of images, where each image of the series is analogous to a section. In this situation, the compression algorithm for an image is dependent on the success of the compression of the previous image in the series.
This adaptive technique has several disadvantages. For example, entropy can often be found in images as a whole, however that entropy may not exist when the image is partitioned into smaller sections. In addition, several attempts may be made to find the proper algorithm, each of which may result in a very poor compression ratio for that section. Since these sections are not recompressed, the compression ratio for the entire image suffers.
Thus, it would be advantageous to provide a system which optimally compresses the image data for storage and/or transfer.
it would furthermore be advantageous to provide a system which automatically and accurately selects the appropriate compression technique for each image.
In addition, it would be advantageous to provide a system which quickly determines the appropriate compression technique for an image transfer.
The present invention provides for these and other advantageous results.